403D - Beautiful Pairs of Numbers - CodeForces Solution

#include <bits/stdc++.h>

using namespace std;

constexpr int N = 1e3+5;
constexpr long long MOD = 1e9 + 7;

int t, n, k, dp[N][N][55];
long long nfac[N], rfac[N];

long long pw(long long n, long long k){
    if(k == 0) return 1;
    if(k == 1) return n % MOD;
    else if(k % 2 == 1){
        long long x = pw(n, k/2);
        return (x * x % MOD) * n % MOD;
    }
    else{
        long long x = pw(n, k/2);
        return (x * x % MOD);
    }
}
long long cnr(long long n, long long r){
    return (nfac[n] * rfac[r] % MOD) * rfac[n-r] % MOD;
}

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);

    nfac[0] = 1; rfac[0] = 1;
    for(int i = 1; i < N; i++){
        nfac[i] = nfac[i-1] * i % MOD;
        rfac[i] = pw(nfac[i], MOD-2);
    }
    dp[0][0][0] = 1;
    for (int i = 0; i < N; i++){
        for (int j = 1; j < N; j++){
            for (int k = 0; k < 55; k++){
                dp[i][j][k] = dp[i][j-1][k];
                if (i >= j && k > 0)
                    dp[i][j][k] = (dp[i][j][k] + dp[i - j][j - 1][k - 1]) % MOD;
            }
        }
    }

    cin >> t;
    while (t--) {
        long long ans = 0;
        cin >> n >> k;
        if (k > 50)
            cout << 0 << '\n';
        else {
            for (int i = 1; i <= n; i++){
                ans =  (ans + (1LL * dp[i][n][k] * cnr(n - i + k, k) % MOD)) % MOD;
            }
            cout << ans * nfac[k] % MOD << '\n';
        }
    }


  return 0;
}